package com.hyb.algorithm.data.struct.dp;

/**
 * @Author: huyanbing
 * @Date: 2021/8/26 10:56 上午
 */
public class IsMatch {

    public static void main(String[] args) {

        String s = "aa", p = "a*";

        IsMatch exe = new IsMatch();

        boolean t = exe.isMatch(s, p);

        System.out.println(t);

    }


    /**
     * dp[i][j]  代表  text[i-len]  是否匹配    j 代表匹配 pattern的j 元素
     *
     * @return
     */
    public boolean isMatch(String text, String pattern) {


        boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];

        // dp[text.length() + 1]=""  dp[pattern.length() + 1]="" 所以是true
        dp[text.length()][pattern.length()] = true;

        for (int i = text.length(); i >= 0; i--) {
            for (int j = pattern.length(); j >= 0; j--) {

                // dp[text.length()][pattern.length()] 已经进行了初始化
                if (i == text.length() && j == pattern.length()) {
                    continue;
                }

                boolean firstMatch = (i < text.length() && j < pattern.length()) && (text.charAt(i) ==
                        pattern.charAt(i)) || (pattern.charAt(i) == '.');


                if (j + 1 < pattern.length() && pattern.charAt(j + 1) == '*') {
                    //一种是 a*aa  a* 可以匹配零次
                    dp[i][j] = dp[i][j + 2] || firstMatch && dp[i + 1][j];
                } else {
                    dp[i][j] = firstMatch && dp[i + 1][j + 1];
                }


            }
        }

        // text 从0开始到结束   pattern 从0开始到结束
        return dp[0][0];
    }
}
